// 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

// 示例 1：

// 输入: "babad"
// 输出: "bab"
// 注意: "aba"也是一个有效答案。
// 示例 2：

// 输入: "cbbd"
// 输出: "bb"


#include "../stdc++.h"

/*
维护一个二维数组dp，其中dp[i][j]表示字符串区间[i, j]是否为回文串，当i = j时，只有一个字符，肯定是回文串，如果i = j + 1，说明是相邻字符，此时需要判断s[i]是否等于s[j]，如果i和j不相邻，即i - j >= 2时，除了判断s[i]和s[j]相等之外，dp[j + 1][i - 1]若为真，就是回文串，通过以上分析，可以写出递推式如下：

dp[i, j] = 1                                   if i == j

         = s[i] == s[j]                        if j = i + 1

         = s[i] == s[j] && dp[i + 1][j - 1]    if j > i + 1 
*/
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int n = s.size();
        bool dp[n][n];
        int left = 0, right = 0, len = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j+1][i-1]));
                if (dp[j][i] && len < i - j + 1) {
                    len = i - j + 1;
                    left = j;
                    right = i;
                }
            }
            dp[i][i] = true;
        }
        return s.substr(left, right - left + 1);
    }
};

// 动态规划
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }
        int maxLen{1};
        int begin{0};
        vector<vector<int>> dp(n, vector<int>(n, 0)); // dp[i][j] 表示 s[i...j]是否是回文串
        for (int i{0}; i < n; ++i) {
            dp[i][i] = true;
        }
        for (int L{2}; L <= n; ++L) { // 先枚举子串长度
            for (int i{0}; i < n; ++i) { // 枚举左边界
                int j = L + i - 1; // 由 L 和 i 可以确定右边界，即 j - i + 1 = L
                if (j >= n) {
                    break;
                }
                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

// 中心扩展算法
class Solution {
public:
    string longestPalindrome(string s) {
        int start{0};
        int end{0};
        int n = s.length();
        for (int i{0}; i < n; ++i) {
            auto p1 = expandAroundCenter(s, i, i);
            auto p2 = expandAroundCenter(s, i, i + 1);
            int left1 = p1.first;
            int right1 = p1.second;
            int left2 = p2.first;
            int right2 = p2.second;
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
private:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return {left + 1, right - 1};
    }
};
